import java.util.*;

/**
 * 179. 最大数
 * https://leetcode-cn.com/problems/largest-number/
 */
public class Solutions_179 {
    public static void main(String[] args) {
        int[] nums1 = {10, 2};  // output: "210"
        int[] nums2 = {3, 30, 34, 5, 9};  // output: "9534330"
        int[] nums3 = {1};  // output: "1"
        int[] nums4 = {10};  // output: "10"
        int[] nums5 = {9, 6, 3, 0, 7, 4, 1, 8, 5, 2};  // output: "9876543210"
        int[] nums6 = {1, 4, 7, 2, 5, 8, 0, 3, 6, 9};  // output: "9876543210"
        int[] nums7 = {0, 0};  // output: "0"

        List<int[]> inputs = new ArrayList<>();
        inputs.add(nums1);
        inputs.add(nums2);
        inputs.add(nums3);
        inputs.add(nums4);
        inputs.add(nums5);
        inputs.add(nums6);
        inputs.add(nums7);

        for (int[] input : inputs) {
            String result = largestNumber(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：排序
     * 以 3 和 10 为例
     * "3" + "10" = "310"
     * "10" + "3" = "103"
     * 而 "310" > "103"，所以 3 排在前
     */
    public static String largestNumber(int[] nums) {
        if (nums == null || nums.length < 1) {
            return "";
        }
        if (nums.length == 1) {
            return String.valueOf(nums[0]);
        }
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        // 排序
        Arrays.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                String s1 = o1 + o2;
                String s2 = o2 + o1;
                // 后减前，降序
                // s2 >= s1，则 o2 在前
                return s2.compareTo(s1);
            }
        });
        // "0000" 的情况
        if ("0".equals(strs[0])) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str);
        }
        return sb.toString();
    }
}
